
public class LinkedList {
    //反转链表
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        //cur从第二个节点开始
        ListNode cur = head.next;
        //将head的后置节点置空
        head.next = null;
        while(cur != null){
            //记录当前需要反转的节点的下一个节点
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
   //找到链表的中间节点
        public ListNode middleNode(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            //原理：当fast的速度是slow的两倍时，fast走到了终点，slow就走到了中点
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
        //返回倒数第k个节点
    public int kthToLast(ListNode head, int k) {
        //这里最好能够判断k的合法性
        //1、fast先走k-1步
        int count = 0;
        ListNode fast = head;
        while(count < k-1){
            fast = fast.next;
            count++;
        }
        //slow和fast一起走
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
    //合并两个有序链表链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode nHead = new ListNode();//不具备有效数据
        ListNode tmp = nHead;

        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                tmp.next = list2;
                list2 = list2.next;
            }
            else{
                tmp.next = list1;
                list1 = list1.next;
            }
            tmp = tmp.next;
        }
        if(list1 != null){
            tmp.next = list1;
        }
        if(list2 != null){
            tmp.next = list2;
        }

        return nHead.next;
    }
    //链表分割，所有小于等于x在前面，大于的在链表后面
    public ListNode partition(ListNode pHead, int x) {
        //1、保证原有顺序不变，建议采用尾插法
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        //遍历完整个链表
        while(cur != null){
            if(cur.val < x){
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //第一个段   没有数据
        if(bs == null){
            return as;
        }
        be.next = as;
        //防止链表循环
        if(as != null){
            ae.next = null;
        }
        return bs;
    }
    //判断链表是否回文
    public boolean chkPalindrome(ListNode A) {
        //1、找到链表的中间节点
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、翻转中间节点以后的链表
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;//记录一下下一个节点
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3、从前、从后开始比较
        //判断条件：1、没有相遇 2、值一样，一旦不一样返回false
        //注意：slow一定在最后一个元素那里，fast不一定
        while(A != slow){
            if(A.val != slow.val){
                return false;
            }
            //解决偶数情况
            if(A.next == slow){
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
    //招到链表的公共节点（如果返回值为null，则说明没有交点）
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1、相交是Y字型
        //2、两个链表长度不同主要体现在相交之前
        //3、可以先让最长的链表先走它们的差值步
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int count1 = 0;
        int count2 = 0;
        //分别求两个链表的长度
        while(cur1 != null){
            count1++;
            cur1 = cur1.next;
        }
        while(cur2 != null){
            count2++;
            cur2 = cur2.next;
        }
        //求出链表的长度差值，让长的先走差值步
        cur1 = headA;
        cur2 = headB;
        int sum = 0;
        if(count1 > count2){
            sum = count1 - count2;
            while(sum > 0){
                cur1 = cur1.next;
                sum--;
            }
        }else{
            sum = count2 - count1;
            while(sum > 0){
                cur2 = cur2.next;
                sum--;
            }
        }
        //一起走直到相遇
        while(cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    //判断链表是否有环
    public boolean hasCycle(ListNode head) {
        //追击问题
        if(head == null)return false;
        ListNode fast = head;
        ListNode slow = head;
        //注意循环条件不是快慢指针相等        防止链表本身没有环
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
    //返回入环的第一个节点
    public ListNode detectCycle(ListNode head) {
        if(head==null) return null;
        ListNode fast = head;
        ListNode slow = head;
        //先让快慢指针相遇判定是否有环
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //如果成立说明没有环
        if(fast == null || fast.next == null){
            return null;
        }
        //结论
        //让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针
        //都是每次均走一步，最终肯定会在入口点的位置相遇。
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    }

//Definition for singly-linked list.
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
